package thired.class10_graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class Class09_Dijkstra {

    public static Map<Node,Integer> dijisktra(Node from){
        HashMap<Node,Integer> distance = new HashMap<>();
        distance.put(from,0);
        HashSet<Node> selected = new HashSet<>();
        Node minNode = getMinNode(distance,selected);
        while (minNode != null){
            int dis = distance.get(minNode);
            for (Edge edge : minNode.edges) {
                Node to = edge.to;
                if(!distance.containsKey(to)){
                    distance.put(to,dis + edge.value);
                }else{
                    distance.put(to,Math.min(distance.get(to),dis+ edge.value));
                }
            }
            selected.add(minNode);
            minNode = getMinNode(distance,selected);
        }
        return distance;
    }

    public static Node getMinNode(HashMap<Node,Integer> distance,HashSet<Node> selected){
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node, Integer> entry : distance.entrySet()) {
            Node node = entry.getKey();
            int dis = entry.getValue();
            if (!selected.contains(node) && dis < minDistance) {
                minNode = node;
                minDistance = dis;
            }
        }
        return minNode;
    }




    public class Record{
        public Node node;
        public int distance;

        public Record(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }

    public class NodeHeap{
       public Node[] nodes;
       public HashMap<Node,Integer> heapIndex;
       public HashMap<Node,Integer> distance;
       public int size;

       public NodeHeap(int size){
            nodes = new Node[size];
            heapIndex = new HashMap<>();
            distance = new HashMap<>();
            size = 0;
       }

        private boolean isEmpty() {
            return size == 0;
        }
        private void swap(int index1,int index2){
            heapIndex.put(nodes[index1], index2);
            heapIndex.put(nodes[index2], index1);
            Node tmp = nodes[index1];
            nodes[index1] = nodes[index2];
            nodes[index2] = tmp;
        }

        private void insertHeapify(int index){
            if(distance.get(nodes[index]) < distance.get(nodes[(index - 1) / 2])){
                swap(index,(index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void heapify(int index,int size){
            int left = index * 2 + 1;
            while (left <= size){
                int smaller = index *2 + 2 < size && distance.get(nodes[left + 1]) < distance.get(nodes[left]) ? left + 1 : left;
                smaller = distance.get(nodes[smaller]) < distance.get(nodes[index]) ? smaller : index;
                if (smaller == index) {
                    break;
                }
                swap(smaller,index);
                index = smaller;
                left = index * 2 + 1;
            }
        }

        private boolean isEntered(Node node) {
            return heapIndex.containsKey(node);
        }

        private boolean inHeap(Node node) {
            return isEntered(node) && heapIndex.get(node) != -1;
        }

        private void addOrUpdateOrIgnore(Node node,int d){
            if(inHeap(node)){//update
                distance.put(node, Math.min(distance.get(node), d));
                insertHeapify(heapIndex.get(node));
            }else{//add
                nodes[size] = node;
                heapIndex.put(node,size);
                distance.put(node,d);
                insertHeapify(size++);
            }
        }
        public Record pop() {
            Record nodeRecord = new Record(nodes[0], distance.get(nodes[0]));
            swap(0, size - 1);
            heapIndex.put(nodes[size - 1], -1);
            distance.remove(nodes[size - 1]);
            // free C++同学还要把原本堆顶节点析构，对java同学不必
            nodes[size - 1] = null;
            heapify(0, --size);
            return nodeRecord;
        }
    }

    public  HashMap<Node, Integer> dijkstra2(Node head, int size){
        NodeHeap nodeHeap = new NodeHeap(size);
        nodeHeap.addOrUpdateOrIgnore(head,0);
        HashMap<Node,Integer> res = new HashMap<>();

        while (!nodeHeap.isEmpty()){
           Record record = nodeHeap.pop();
           Node cur = record.node;
           int dis = record.distance;

            for (Edge edge : cur.edges) {
                nodeHeap.addOrUpdateOrIgnore(edge.to, edge.value + dis);
            }
            res.put(cur,dis);
        }
        return res;
    }
}
